#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <cstring>

using namespace std;

const unsigned int N = 256;
const unsigned int M = 2 * N;
const unsigned long long MAX = 0xffffffffffff;

class Buffer {
public:
    unsigned int bits = 0;
    char ch = 0;
};

class HuffmanTree;

class TreeNode {
    friend HuffmanTree;
private:
    unsigned long long weight = 0;
    unsigned int right = N - 1, left = N - 1;
    unsigned int parents = N - 1;
};

class HuffmanTree {
private:
    TreeNode nodes[M];
    unsigned int leaf[N];
    unsigned int index[N];
    vector<char*> leafCode;
    ifstream input;
    ofstream output;
    unsigned int num = 0;
    unsigned long long size = 0;
    Buffer buf;

    void writeBit(unsigned int bit);
    void writeBits(unsigned int target, unsigned int bits);
    void writeRest();
    void readBit(unsigned int &bit);
    void readBits(unsigned int &target, unsigned int bits);
    void deSieve();

public:
    void Decode();
};

void HuffmanTree::writeBit(unsigned int bit) {
    buf.ch = (buf.ch << 1) | bit;
    buf.bits++;
    if (buf.bits == 8) {
        output.put(buf.ch);
        buf.bits = 0;
        buf.ch = 0;
    }
}

void HuffmanTree::writeBits(unsigned int target, unsigned int bits) {
    stack<unsigned int> s;
    for (unsigned int i = 0; i < bits; ++i) {
        s.push(target & 1);
        target >>= 1;
    }
    while (!s.empty()) {
        writeBit(s.top());
        s.pop();
    }
}

void HuffmanTree::writeRest() {
    while (buf.bits < 8) {
        writeBit(0);
    }
}

void HuffmanTree::readBit(unsigned int &bit) {
    if (buf.bits == 0) {
        input.read(&buf.ch, 1);
        buf.bits = 8;
    }
    bit = (buf.ch & 128) >> 7;
    buf.bits--;
    buf.ch <<= 1;
}

void HuffmanTree::readBits(unsigned int &target, unsigned int bits) {
    target = 0;
    unsigned int tmp;
    for (unsigned int i = 0; i < bits; ++i) {
        readBit(tmp);
        target = (target << 1) | tmp;
    }
}

void HuffmanTree::deSieve() {
    string inName, outName;
    cin >> inName;
    outName = inName;
    size_t dotPos = outName.find_last_of('.');
    if (dotPos != string::npos) {
        outName.replace(dotPos, outName.length() - dotPos, ".txt");
    } else {
        outName.append(".txt");
    }

    input.open(inName, ios::binary);
    if (!input.is_open()) {
        cerr << "Cannot open file: " << inName << endl;
        exit(1);
    }
    
    output.open(outName, ios::binary);
    if (!output.is_open()) {
        cerr << "Cannot open output file: " << outName << endl;
        exit(1);
    }

    input.read(reinterpret_cast<char*>(&size), sizeof(unsigned long long));
    readBits(num, 8);
    if (num == 0) num = 256;

    for (unsigned int i = 0; i < num; ++i) {
        input.read(reinterpret_cast<char*>(&index[i]), sizeof(char));
    }

    unsigned int maxBit = 1;
    unsigned int tmp = num * 2 - 1;
    while (tmp) {
        maxBit++;
        tmp >>= 1;
    }

    for (unsigned int i = num; i < num * 2 - 1; ++i) {
        readBits(nodes[i].left, maxBit);
        readBits(nodes[i].right, maxBit);
        nodes[nodes[i].left].parents = nodes[nodes[i].right].parents = i;
    }
}

void HuffmanTree::Decode() {
    deSieve();

    unsigned int tmp;
    readBit(tmp);

    unsigned int loc;
    for (unsigned long long i = 0; i < size; ++i) {
        loc = 2 * num - 2;
        while (nodes[loc].left != N - 1 || nodes[loc].right != N - 1) {
            if (tmp == 0) loc = nodes[loc].left;
            else loc = nodes[loc].right;
            readBit(tmp);
        }
        output.put(index[loc]);
    }

    cout << "Done!\n" << endl;
    input.close();
    output.close();
}

int main() {
    HuffmanTree tree;
    tree.Decode();
    return 0;
}

